package com.roy.galaxy.algorithm;

/**
 * @author gang.wang1903@xiaobao100.cn
 * @Date: 2019-09-16 19:21
 */
public class MergeSort {


    private static void merge(Integer[] array,final int left,final int leftEnd, final int rightEnd){
        Integer[] mergeResult = new Integer[rightEnd-left+1];
        int i = 0; //mergeResult的下标
        int j = left; //left 的下标
        int k = leftEnd+1; //right 的下标

        //将两个数组中较小的元素拷贝到mergeResult中

        while(j<=leftEnd&&k<=rightEnd){
            if(array[j]<array[k]){
                mergeResult[i++] = array[j++];
            }else{
                mergeResult[i++] = array[k++];
            }
        }
        //将另一个数组中剩余的元素拷贝到mergeResult中
        while(j<=leftEnd){
            mergeResult[i++] = array[j++];
        }
        while(k<=rightEnd){
            mergeResult[i++] = array[k++];
        }
        //copy mergeResult to array
        int leftPos = left;
        for(int m=0;m<mergeResult.length;m++,leftPos++){
            array[leftPos] = mergeResult[m];
        }
    }


    private static void print(Integer[] array) {
        if (array == null) {
            throw new NullPointerException("The array can not be null !!!");
        }
        StringBuilder sb = new StringBuilder("[");
        for (int element : array) {
            sb.append(element + ", ");
        }
        sb.replace(sb.length() - 2, sb.length(), "]");
        System.out.println(sb.toString());
    }



    private static void mergeSort(Integer[] array,final int left,final int leftEnd, final int rightEnd){
        if(left>=rightEnd){
            return;
        }
        mergeSort(array,left,(left+leftEnd)/2,leftEnd);
        mergeSort(array,leftEnd+1,(leftEnd+1+rightEnd)/2,rightEnd);
        merge(array,left,leftEnd,rightEnd);
    }


    public static void mergeSort(Integer[] array){
        mergeSort(array,0,(array.length)/2,array.length-1);
    }


    public static void main(String[] args) {
        Integer original[] = new Integer[] { 6, 10, 25, 3, 33, 90, 60, 100, 56 };
        mergeSort(original);
        print(original);
    }






}
